package code.oldCode.feishuSpecializedTraining.string;

import java.util.Arrays;

/**
 * @author 26029
 * @date 2025/3/9
 * @description
 */
public class MyString2 {
    // 28. 找出字符串中第一个匹配项的下标
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty())
            return 0;
        // 直接用 KMP
        int len = haystack.length();
        int needleLen = needle.length();
        int j = 0;
        int[] next = getNext(needle);
        for (int i = 0; i < len; i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i))
                j = next[j - 1];
            if (needle.charAt(j) == haystack.charAt(i))
                j++;
            if (j == needleLen)
                return i - j + 1;
        }
        return -1;
    }
    public int[] getNext(String needle) {
        int len = needle.length();
        int[] next = new int[len];
        int j = 0;
        for (int i = 1; i < len; i++) {
            while (j > 0 && needle.charAt(j) != needle.charAt(i))
                j = next[j - 1];
            if (needle.charAt(j) == needle.charAt(i))
                j++;
            next[i] = j;
        }
        return next;
    }

    // 459. 重复的子字符串
    public boolean repeatedSubstringPattern(String s) {
        // 拼接自身，去掉首位元素，看包不包含自身
        String str = s + s;
        return str.substring(1, str.length() - 1).contains(s);
    }

    public static void main(String[] args) {
        MyString2 myString2 = new MyString2();
        System.out.println(Arrays.toString(myString2.getNext("aabaaf")));
    }
}
